package LearnAlgorithm.d_标准查找算法and标准排序算法;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-18 19:17
 * @description: LeetcodeLearnAlgorithm -> LearnAlgorithm.d_标准查找算法and标准排序算法
 */
/*

log M   除以  log N
   e            e

等于

log M
   N


Math.log(x)
返回x以e为底的对数，返回数值的类型是double。
Math.floor(x)
向上取整的四舍五入，Math.floor(5.1) = 6


int x = 1 << y
x代表2^y


满二叉树，设根节点算第1层
那么从root到第n层，总共的节点个数是(2^n - 1)个
4层满二叉树的节点是2^4 - 1 = 15个

对于完全二叉树，假设我们利用m个节点制作成满二叉树，最终结果会有

(log m)(对这个对数进行向下取整) + 1   层
(   2 )

log 15 = 3.9.... 即3 + 1 = 4层
   2
 */
public class a4RMQ区间查找 {

    /**
     * 构建ST表O(NlogN)
     * @param arr
     * @return
     */
    public static Result createMatrix(int[] arr) {
        int length = arr.length;
        int treeLayer = (int)Math.floor(Math.log(length) / Math.log(2)) + 1;
        int[][] minMatrix = new int[length][treeLayer];
        int[][] maxMatrix = new int[length][treeLayer];

        for (int i = 0; i < length; i++) {
            minMatrix[i][0] = arr[i];//[i][0]代表2^0,即区间长度是2^0,自己到自己；自己到自己的范围求极值，那就是自己
            maxMatrix[i][0] = arr[i];
        }

        /*
        动态规划，开始填表
        其中 minn[i][j] 表示
         A 中从下标 i 开始、连续 2^j 个元素所组成的区间的最小值，
         maxn[i][j] 表示
         A 中从下标 i 开始、连续 2^j 个元素所组成的区间的最大值。
         最终返回的就是这两个矩阵。
         */
        int j = 1;//j不从0开始是因为，j=0的情况，我们在上面的for循环中已经算过了
        while (j < treeLayer) {//j最大是treeLayer - 1
            /*
            int x = 1 << j,结果x = 2^j是区间长度
            区间长度包括起始元素和结束元素
            所以上面，当2^0 = 1 的时候，区间长度是1，我们说的是”自己到自己“
            i最大只能到 length - (1 << j) + 1 - 1,也就是说，i < (length - (2^j) + 1);这个是推导出来的
            如果i==(length - (2^j) + 1)，那么”i+区间长度“ 就会超过了表格，越界了！
             */
            /*for (int i = 0; i < length; i++) {//每一行的所有位置全部填上
                //定义一半的个数
                int half = (1 << (j - 1));
                if (i + half < length) {
                    //最小值 = min(i~一半(即前半段)的最小值 , i+一半(后半段)的最小值)
                    minMatrix[i][j] = Math.min(minMatrix[i][j-1],minMatrix[i + half][j - 1]);
                    //比如一开始是max(maxMatrix[i=0][j-1=0],maxMatrix[i + half=0+1=1][j - 1=0]),每两个数就比一次大小
                    maxMatrix[i][j] = Math.max(maxMatrix[i][j-1],maxMatrix[i + half][j - 1]);
                }
            }*/
            for (int i = 0; i < (length - (1 << j) + 1); i++) {//每一行的所有位置全部填上
                //最小值 = min(i~一半(即前半段)的最小值 , i+一半(后半段)的最小值)
                minMatrix[i][j] = Math.min(minMatrix[i][j-1],minMatrix[i + (1 << (j - 1))][j - 1]);
                //比如一开始是max(maxMatrix[i=0][j-1=0],maxMatrix[i + half=0+1=1][j - 1=0]),每两个数就比一次大小
                maxMatrix[i][j] = Math.max(maxMatrix[i][j-1],maxMatrix[i + (1 << (j - 1))][j - 1]);
            }
            j++;
        }
        return new Result(minMatrix,maxMatrix);
    }

    static public class Result {
        public int[][] minMatrix;//dp矩阵，最后一行是查找结果的行
        public int[][] maxMatrix;//dp矩阵，最后一行是查找结果的行

        public Result(int[][] minMatrix, int[][] maxMatrix) {
            this.minMatrix = minMatrix;
            this.maxMatrix = maxMatrix;
        }

        /**
         * 最后一行，是根据i,j决定的
         * 具体实现方法是通过区间长度 j-i+1 计算需要向上取整的 log2 值作为树的层数，
         * 通过 1 << logSize 计算出区间的二分法范围，
         * 并在 minn 和 maxn 中查找区间最小值和最大值。
         * O(1)
         * @param i
         * @param j
         * @return
         */
        public int maxQuery(int i, int j) {
            //当前区间元素个数
            int elementSize = j - i + 1;
            //以元素个数为节点个数，生成的完全二叉树的（层数-1），在数值上就是treeLayers
            //另一个角度，在ST表中查询的最大层数就是treeLayers
            int treeLayers = (int) Math.floor(Math.log(elementSize) / Math.log(2));
            /*
            1 << treeLayers == 2^treeLayers
            [i][treeLayers] ................... [j - (2^treeLayers - 1)][treeLayers]
            有重叠，但不影响查找极值
             */
            return Math.max(maxMatrix[i][treeLayers],maxMatrix[j - (1 << treeLayers) + 1][treeLayers]);
        }

        public int minQuery(int i, int j) {
            int elementSize = j - i + 1;
            int treeLayers = (int)Math.floor(Math.log(elementSize) / Math.log(2));
            return Math.min(minMatrix[i][treeLayers],minMatrix[j - (1 << treeLayers) + 1][treeLayers]);
        }
    }
}
